#include <stdio.h>
#include <stdlib.h>
#include <wlist.h>

/*无头不循环单链表
 *
 */

/*1.链表逆置
 *头插法
 *三指针法
 */

//头插法
void reverse()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	

	List_st *p = list->next;
	List_st *cur = NULL;

	//保存当前结点的值和下一个结点，将当前结点删除，再插入头部
	while(p)
	{
		List_st *q = NULL;
		q = malloc(sizeof(*q));
		q->data = p->data;
		cur = p->next;

		list_delete(list,&(p->data));
		list_insert_head(&list,q);
		p = cur;
	}

	list_display(list);	


}

//三指针法
void reverse_3()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	

	List_st *first = NULL;
	List_st *mid = list;
	List_st *last = list->next;

	while(mid)
	{
		mid->next = first;
		first = mid;
		mid = last;

		if(last)
		{
			last = last->next;
		}
	}
	list = first;	
	list_display(list);	

}

/*两条有序链表合并，链表依旧有序
 *
 */
void list_union()
{
	List_st *list1 = NULL;
	list_create(&list1,order);
	list_display(list1);	

	List_st *list2 = NULL;
	list_create(&list2,order);
	list_display(list2);

	while(list2)
	{
		List_st *p = NULL;
		p = malloc(sizeof(*p));
		if(p == NULL)
			return ;
		p->data = list2->data;
		list_insert_order(&list1,p);
		list2 = list2->next;
	}
		list_display(list1);	
}

/*返回链表的倒数第x个结点
 *让q指针先跑x-1个结点，然后一起跑，直到q到最后一个结点
 */

void backwards_x()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	
	
	List_st *p = list;
	List_st *q = list;
	
	int x,i;
	printf("Please input x:\n");
	scanf("%d",&x);

	for(i = 0;i < x-1;i++)
		q = q->next;
	while(q->next)
	{
		p = p->next;
		q = q->next;
	}
	printf("%d\n",p->data);
}


/*返回链表的中间结点的值
 *
 *
 */

void middle_value()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	
	
	List_st *p = list;
	List_st *q = list;

	//q->next 和 q->next->next 顺序不能相反	
	while(q->next && q->next->next)
	{
		p = p->next;
		q = q->next->next;
	}
	printf("%d\n",p->data);
}


/*反序输出链表中的值
 *1,索引数组
 *2,递归输出
 */

void antitone()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	
	
	List_st *ptr = list;

	int *p = NULL;
	int k = 0,n = 100;
	p = calloc(n,sizeof(Datatype));

	while(ptr)
	{
		p[k++] = ptr->data;
		ptr = ptr->next;
	}
	--k;

	for(int i = k;i >= 0;i--)
	{
		printf("%d ",p[i]);
	}
	printf("\n");
}


void r_antitone(List_st *ptr)
{
	if(ptr == NULL)
		return ;
	r_antitone(ptr->next);
	printf("%d ",ptr->data);

}
/*判断链表是否有环
 *
 */

void Isloop()
{
	List_st *list = NULL;
	list_create(&list,end);
	
	List_st *p = list;
	List_st *q = list;
	int flag = 0;
	while(q->next && q->next->next)
	{
		p = p->next;
		q = q->next->next;
		if(p == q)
		{
			flag = 1;
			break;
		}
	}
	if(flag)
		printf("list is loop!\n");
}


/*删除链表中最小的值
 *
 */


void de_min()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	

	List_st *cur = list->next;
	
	List_st *min = list;
	while(cur)
	{
		if(cur->data < min->data)
		{
			min = cur;
		}
		cur = cur->next;
	}
	list = list_delete(list,&(min->data));	
	list_display(list);	
}

/*链表实现大数据相加
 *
 */

void max_add()
{
	List_st *list1 = NULL;
	list_create(&list1,head);
	
	printf("--------------------\n");

	List_st *list2 = NULL;
	list_create(&list2,head);
	
	List_st *p = list1;
	List_st *q = list2;
	List_st *cur = NULL;
	while(p && q)
	{
		if((p->data + q->data) < 10)
		{
			p->data += q->data;
		}
		else
		{
			p->data = (p->data + q->data) % 10;
			p->next->data += 1;
		}
		cur = p;
		p = p->next;
		q = q->next;
	}
	if(p == NULL && q != NULL)
	{
		cur->next = q;	
	}
	printf("======================\n");
	r_antitone(list1);

}

/*判断A是否为B的子序列
 *
 */

void A_B()
{
	List_st *list1 = NULL;
	list_create(&list1,end);
	
	printf("--------------------\n");

	List_st *list2 = NULL;
	list_create(&list2,end);
	
	List_st *p = list1;
	List_st *q = list2;
	
	while(p)
	{
		q = list2;
		while(q && p->data == q->data)
		{
			p = p->next;
			q = q->next;
		}
		if(q == NULL)
		{
			printf("Yes!\n");
			break;
		}
		p = p->next;
	}
	
}

/*把链表中的负数放在链表前面
 *1，头插法
 *2，pz指向第一个正数，pf指向第一个负数，然后交换值域
 */

	void minus()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	
	
	List_st *ptr = list;
	List_st *pf = NULL;
	List_st *pz = NULL;
	//代替ptr向下移动
	List_st *p = NULL;
	int temp;

	while(ptr)
	{
		if(ptr->data > 0)
		{
			pz = ptr;
			//p从上次的负数位置向下找，因为前面已经是替换后的负数
			if(pf)
				p = pf;
			else
				p = pz;
			while(p)
			{
				if(p->data < 0)
				{
					pf = p;
					temp = pf->data;
					pf->data = pz->data;
					pz->data = temp;
					break;
				}
				p = p->next;
			}
			//p为空证明链表已经没有可置换的负数
			if(p == NULL)
				break;
		}
		ptr = ptr->next;
	}
	list_display(list);	
}

/*链表排序:
 * 插入排序
 * 冒泡排序
 *
 */

    void list_sort()
{
	List_st *list = NULL;
	list_create(&list,end);
	list_display(list);	
	
	List_st *ptr = list;
	List_st *p = list;
	int temp = 0;

	while(p)
	{
		while(ptr->next)
		{
			if(ptr->data > ptr->next->data)
			{
				temp = ptr->data;
				ptr->data = ptr->next->data;
				ptr->next->data = temp;
			}
			ptr = ptr->next;	
		}
		p = p->next;
	}	
	list_display(list);	
}


void union_AB()
{
	List_st *list1 = NULL;
	list_create(&list1,end);
	
	printf("--------------------\n");

	List_st *list2 = NULL;
	list_create(&list2,end);
	
	int a[100] = {0};
	int k = 0;
	List_st *p = list1;
	List_st *q = list2;
	
	while(p)
	{
		q = list2;
		while(q)
		{
			if(p->data == q->data)
			{
				a[k++] = p->data;
			}
			q = q->next;
		}
		p = p->next;
	}
	for(int i = 0;i < k;i++)
	{
		printf("%d ",a[i]);
	}
	printf("\n");	
}	

int main()
{
	//	reverse();
	//	reverse_3();
	//	list_union();

	//	backwards_x();
	//	middle_value();
	/*	
		List_st *list = NULL;
		list_create(&list,end);
		list_display(list);	
		r_antitone(list);
	*/	
	//	antitone();
	//	Isloop();
	//	de_min();
	//	max_add();
	//	A_B();
	//	minus();
	//	list_sort();
		union_AB();	
	exit(0);
}
